class ListDict:
    """
    ListDist是一个元素的集合，它既可以像List一样通过下标访问元素，又可以像Dict一样通过键值访问元素。
    """
    def __init__(self):
        self._head = _Node()
        self._head.prev = self._head
        self._head.next = self._head
        self._num = 0
        self._dict = {}

    def __len__(self):
        return self._num

    def __iter__(self):
        head = self._head
        p = head.next
        while p is not head:
            yield p.key, p.value
            p = p.next

    def items(self):
        return self._dict.items()

    def keys(self):
        head = self._head
        p = head.next
        while p is not head:
            yield p.key
            p = p.next

    def values(self):
        head = self._head
        p = head.next
        while p is not head:
            yield p.value
            p = p.next

    def __contains__(self, item):
        return item in self._dict

    def add(self, key, value=None):
        return self.append(key, value)

    def append(self, key, value=None):
        assert key not in self._dict

        node = _Node(key, value)
        tail = self._head.prev
        node.prev = tail
        tail.next = node
        node.next = self._head
        self._head.prev = node
        self._dict[key] = node
        index = self._num
        self._num += 1
        return index

    def insert(self, index, key, value=None):
        assert index >= 0
        assert key not in self._dict
        index0 = index
        head = self._head
        p = head.next
        while p is not head and index > 0:
            p = p.next
            index -= 1
        if index > 0:
            raise IndexError('index out of bounds %s >= %d' % (index0, len(self)))

        node = _Node(key, value)
        p.prev.next = node
        node.prev = p.prev
        node.next = p
        p.prev = node
        self._dict[key] = node
        self._num += 1

    def insert_by_order(self, key, func, value=None):
        """
        利用函数func对比键的大小，然后把key插入到相应位置。插入时假设当前所有的键已经从小到大排序
        :param key: 当前准备插入的key
        :param func: func函数形如f(k, v)，其中k和v是当前队列中的键及其对应的值，如果k < key返回值应该小于0；
        如果k==key应该返回0，否则返回大于0的值。
        :param value: key所对应的值value
        :return: 返回key的位置，从0开始数
        """
        assert key not in self._dict
        p = self._head.next
        index = 0
        while p is not self._head and func(p.key, p.value) < 0:
            p = p.next
            index += 1

        node = _Node(key, value)
        p.prev.next = node
        node.prev = p.prev
        node.next = p
        p.prev = node
        self._dict[key] = node
        self._num += 1
        return index

    def pop(self, index):
        assert index >= 0
        index0 = index
        head = self._head
        p = head.next
        while True:
            if p is head:
                raise IndexError('index out of bounds %s >= %d' % (index0, len(self)))
            if index == 0:
                del self._dict[p.key]
                p.prev.next = p.next
                p.next.prev = p.prev
                self._num -= 1
                return p.key, p.value
            p = p.next
            index -= 1

    def __delitem__(self, key):
        """
        等价于调用self.remove(key)
        :param key:
        """
        self.remove(key)

    def remove(self, key):
        node = self._dict[key]
        del self._dict[key]
        node.prev.next = node.next
        node.next.prev = node.prev
        self._num -= 1

    def __getitem__(self, key):
        return self._dict[key].value

    def value(self, index):
        assert index >= 0
        index0 = index
        head = self._head
        p = head.next
        while True:
            if p is head:
                raise IndexError('index out of bounds %s >= %d' % (index0, len(self)))
            if index == 0:
                return p.key, p.value
            p = p.next
            index -= 1

    def __repr__(self):
        result = []
        for key, value in self:
            result.append('%s: %s' % (key, value))
        return '{' + ', '.join(result) + '}'


class _Node:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None


if __name__ == '__main__':
    s = ListDict()
    print(s)
    s.append('aa', 'a1111')
    print(s)
    s.append('bb', 22222)
    print(s)
    s.append('cc', 3333)
    print(s)
    print(s.value(0))
    print('aa' in s)
    s.pop(0)
    print(s)
    print('aa' in s)
    s.pop(1)
    print(s)
    print('bb' in s)
    print('cc' in s)
    print('-' * 20)
    s.remove('bb')
    print(s)
    print('bb' in s)
    s.append('aa', '11aa11')
    s.append('aaa', '111aaa111')
    print(s)
    s.pop(1)
    print(s, len(s))
